The invention relates to the design and manufacture of integrated circuits. An integrated circuit (IC) has a large number of electronic components, such as transistors, logic gates, diodes, and wires, which are fabricated by forming layers of different materials and of different geometric shapes on various regions of a silicon wafer. Many phases of physical design may be performed with computer aided design (CAD) tools or electronic design automation (EDA) systems. To design an integrated circuit, a designer first creates high level behavior descriptions of the IC device using a high-level hardware design language. An EDA system typically receives the high level behavior descriptions of the IC device and translates this high-level design language into netlists of various levels of abstraction using a computer synthesis process. A netlist describes interconnections of nodes and components on the chip and includes information of circuit primitives such as transistors and diodes, their sizes and interconnections, for example.
An integrated circuit designer may use a set of layout EDA application programs to create a physical integrated circuit design layout from a logical circuit design. The layout EDA application uses geometric shapes of different materials to create the various electrical components on an integrated circuit and to represent electronic and circuit IC components as geometric objects with varying shapes and sizes. After an integrated circuit designer has created an initial integrated circuit layout, the integrated circuit designer then verifies and optimizes the integrated circuit layout using a set of EDA testing and analysis tools. Verification may include, for example, design rule checking to verify compliance with rules established for various IC parameters.
Typically, geometric information about the placement of the nodes and components onto the chip is determined by a placement process and a routing process. The placement process is a process for placing electronic components or circuit blocks on the chip and the routing process is the process for creating interconnections between the blocks and components according to the specified netlist.
The task of all routers is the same—routers are given some pre-existing polygons consisting of pins on cells and optionally some pre-routes from the placers to create geometries so that all pins assigned to different nets are connected by wires and vias, that all wires and vias assigned to different nets do not overlap, and that all design rules are obeyed. That is, a router fails when two pins on the same net that should be connected are open, when two pins on two different nets that should remain open are shorted, or when some design rules are violated during routing.
One of the early routing algorithms is the Lee algorithm, which is also commonly called the maze routing algorithm. The Lee algorithm is known to find a route if one exists. Nonetheless, the Lee algorithm is also known to be slow and memory intensive. As such, the application of the base Lee algorithm to electronic designs over a certain size is oftentimes impractical. Moreover, the Lee algorithm approach often breaks down if there is a large number of nets or sets of nets that need to be routed over a design.
One widely adopted solution for the impracticality of the Lee algorithm is the introduction of a two-level global routing, which decides the rough route for each net, followed by detailed routing. As global routing is performed to determine an approximate route for each wire, it is much faster than pure maze routing under the Lee algorithm. In addition to determining the rough route for each net, the objectives of global routing are typically to minimize the routing congestion and the total wirelength. After the global routing is complete, each area defined by each global cell or gcell (which may be referred to herein as a “grid”) is then detailed routed by a detailed router.
Three-level routing may also be employed to route an electronic design. In this approach, “C-routing” (which refers to either corridor-routing or conduit-routing) is performed between the global and detailed routing actions. C-routing is performed to coordinate assignments for routes which cross one or more global cell boundaries defined during the global routing stage. Thus, C-routing will determine the major part or trunk of a route which cross multiple global cells, leaving mostly short connection within a global cell to be handled by the detail router. The three-level routing technique provides a very effective “divide and conquer” approach for routing that allows each of the three levels of routers to effectively handle a manageable portion of the hierarchy of routing tasks.
The usual medium of communication between the IC design engineers and the foundry is through a set of design rules. The design rules provide design parameters and guidelines in an attempt to make sure that designers create IC designs which are manufacturable and will function for intended purposes. For example, the IC fabrication facility may provide spacing rules that specific the minimum spacing between any two objects in an IC design layout.
The design rules may be categorized into two types. The first type is called hard rules which are the design rules that must be obeyed in the IC design for fabrication/manufacturability. The second type is called soft rules or preferred rules which improve one or more factors such as timing, manufacturability, or yield but are not required to be always met. While a designer may almost always desire the soft rule to be used to implement a design, there may be design constraints or layout restrictions that require the designer to instead create a design that comply with the hard rules.
Therefore, one common problem faced by a router is the situation when both the hard rules and the preferred rules need to be considered during the design process. In many cases, it is very difficult for a router to effectively and efficiently understand how to balance the need to comply with hard rules while also attempting to implement a design using soft rules. At the global router level, one approach that can be taken to address hard and soft rules is described in U.S. patent application Ser. No. 11/838,195, filed on Aug. 13, 2007, which is hereby incorporated by reference in its entirety.
However, this problem cannot be efficiently and effectively managed at the detail router level. Quite simply, the quantity and complexity of analysis and management that needs to be performed to adequately consider both hard and soft rules at the detail router level is unmanageable with conventional design techniques.
Embodiments of the present invention provide an approach for perform C-routing which can simultaneously consider and balance both hard and soft rules when implementing C-routes for a design. By performing these actions during the C-routing process, this avoids (either in part or in its entirety) the complexity of having to simultaneously consider these types of rules during detail routing. Both hard rules and soft rules can be concurrently considered during C-routing to perform routing/track assignments across global cells as well as to route longer segments in the design.
Further details of aspects, objects, and advantages of the invention are described below in the detailed description, drawings, and claims. Both the foregoing general description and the following detailed description are exemplary and explanatory, and are not intended to be limiting as to the scope of the invention.